/*
 Clase WrapperHeap que implementa WordSet para guardar
 las palabras ingresadas. 
 Autor: Paola Garcia, carnet 10205
 Tomado como referencia el codigo proporcionado por el libro de Java Structures y 
 el trabajo de Juan Carlos Rosito.
 
 
 Se utilizo un Heap para la implementacion del mismo, ya que posee una forma rapida
 de busqueda en la lista, tambien usa poca memoria para guardar los datos y las
 operaciones a realizar durante todo el listado que sea ingresado o no. Una desvenaja
 es que no es tan rapido como otros, ya que posee distintas operaciones para poder
 colocar un nuevo elemento en el arbol e ir corriendo los distintos para que el
 arbol no sea modificado en orden o logica durante la inserccion de datos o al
 extraer datos. 
 
 */

import java.util.*;

class WrapperHeap implements WordSet{
	//se crea un vector para guardar los datos ingresados
    protected Vector<Word> lista;

    //constructor
    public WrapperHeap(){
        
        lista = new Vector<Word>();
        
    }
    
    //se genera el padre del arbol a generar con las palabras
     protected static int parent(int i){
        return (i-1)/2;
    }
     
     //se indica para donde debe guardarse si debe ir a la izquierda
     protected static int right(int i){
         return 2*(i+1);
     }
    
     //se indica para donde debe guardarse si debe ir a la derecha
    protected static int left(int i){
        return 2*i+1;
    }
    
    //para subir el data si es necesario
    protected void percolateUp(int leaf){
        leaf=leaf-1;	//se indica la hoja
        int papa = parent(leaf);
        Word value = lista.get(leaf);	//de agrega a la hoja el nombre
        while (leaf > 0 && (value.compareTo(lista.get(papa)) < 0)){
            lista.set(leaf,lista.get(papa));
            leaf = papa;	//se coloca el nuevo padre
            papa = parent(leaf);
        }
        lista.set(leaf,value);
    }
	
    //agregar un nuevo dato del arbol
    public void add(Word wordObject){
        lista.add(wordObject);
        percolateUp(lista.size());
    }

    
    //sacar un dato del arbol
    public Word get(Word word){
		int index = lista.indexOf(word);
		if(index == -1) return null;
		return lista.get(index);
	}

	@Override
	public String get(Object word) {
		// TODO Auto-generated method stub
		return null;
	}
	          
}
